package club.xiaojiawei.binarytree;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/15/22 6:42 PM
 * @question 106. 从中序与后序遍历序列构造二叉树
 * @description 给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
 */
public class BuildTree106 {

    public static void main(String[] args) {
        TreeNode result = buildTree(new int[]{9, 3, 15, 20, 7}, new int[]{9, 15, 7, 20, 3});
        System.out.println(result);
    }

    static int postIdx;
    static int[] postOrder;
    static int[] inOrder;
    static Map<Integer, Integer> idxMap = new HashMap<Integer, Integer>();

    public static TreeNode helper(int inLeft, int inRight) {
        // 如果这里没有节点构造二叉树了，就结束
        if (inLeft > inRight) {
            return null;
        }
        // 选择 post_idx 位置的元素作为当前子树根节点
        int rootVal = postOrder[postIdx];
        TreeNode root = new TreeNode(rootVal);
        // 根据 root 所在位置分成左右两棵子树
        int index = idxMap.get(rootVal);
        // 下标减一
        postIdx--;
        // 构造右子树
        root.right = helper(index + 1, inRight);
        // 构造左子树
        root.left = helper(inLeft, index - 1);
        return root;
    }

    /**
     * 官方-递归
     * @param inOrder
     * @param postOrder
     * @return
     */
    public static TreeNode buildTree(int[] inOrder, int[] postOrder) {
        BuildTree106.postOrder = postOrder;
        BuildTree106.inOrder = inOrder;
        // 从后序遍历的最后一个元素开始
        postIdx = postOrder.length - 1;
        // 建立（元素，下标）键值对的哈希表
        int idx = 0;
        for (Integer val : inOrder) {
            idxMap.put(val, idx++);
        }
        return helper(0, inOrder.length - 1);
    }

    /**
     * 官方-迭代(没理解透彻)
     * @param inorder
     * @param postorder
     * @return
     */
    @SuppressWarnings("all")
    public static TreeNode buildTree2(int[] inorder, int[] postorder) {
        if (postorder == null || postorder.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[postorder.length - 1]);
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        stack.push(root);
        int inorderIndex = inorder.length - 1;
        for (int i = postorder.length - 2; i >= 0; i--) {
            int postorderVal = postorder[i];
            TreeNode node = stack.peek();
            if (node.val != inorder[inorderIndex]) {
                node.right = new TreeNode(postorderVal);
                stack.push(node.right);
            } else {
                while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
                    node = stack.pop();
                    inorderIndex--;
                }
                node.left = new TreeNode(postorderVal);
                stack.push(node.left);
            }
        }
        return root;
    }

    static class TreeNode{

        private int val;

        private TreeNode left;

        private TreeNode right;

        public TreeNode() {
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        public TreeNode(int val) {
            this.val = val;
        }

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }

        public TreeNode getLeft() {
            return left;
        }

        public void setLeft(TreeNode left) {
            this.left = left;
        }

        public TreeNode getRight() {
            return right;
        }

        public void setRight(TreeNode right) {
            this.right = right;
        }
    }
}
